/**
 * 组合总和III --使用一次，限制k层
找出所有相加之 **和为n** 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：所有数字都是正整数。解集不能包含重复的组合。【无序】
输入: k = 3, n = 7 输出: [[1,2,4]]
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
/**
 * 【终止条件】
 * 1 path.length == k
 * 2 sum == n 放入剪枝规则中
 */
var combinationSum3 = function(k, n) {
  const res= [];
  const path = []
  const backTrack = (sum, index) => {
    if(path.length == k && sum == n) {
      res.push(path.slice());
      return;
    }
    for(let i=index; i<=9-k+path.length+1;i++) {
      if(sum+i>n)break;
      path.push(i);
      backTrack(sum+i, i+1);
      path.pop();
    }
  }
  backTrack(0, 1);
  return res;
};
// const k = 3, n = 7;
const k = 3, n = 9;
console.log('组合总和III',combinationSum3(k,n)); 
//[[1,2,4]]  
//[[1,2,6], [1,3,5], [2,3,4]]